我们应该用缩点,将原图变为图,同时记录每个强连通分量的节点个数,记为。
因为起点终点都是1,所以路径一定是一个环。我们可以处理出1到所有点的距离,存在中(跑正图)和所有点到1的距离存在中(跑反图)。注意,如果走不到就设为极小值。最短路跑的是点权,其实和边权差不多。
题目说可以逆向走一条有向边,我们设该边起点为,终点为,那么,答案就应为。
#include <cstdio>
#include <queue>
#include <stack>
#include <cstring>
#include <iostream>
using namespace std;
const int MAXN = 100000;
int n,m,x,y;
vector< int > Graph[ MAXN + 5 ];
stack< int > s;
int dfn[ MAXN + 5 ] , low[ MAXN + 5 ] , depth , cnt;
int belong[ MAXN + 5 ] , num[ MAXN + 5 ];
bool is[ MAXN + 5 ];
void Tarjan( int u ) {
dfn[ u ] = low[ u ] = ++ depth;
is[ u ] = 1 , s.push( u );
int v;
for( int i = 0 ; i < Graph[ u ].size( ) ; i ++ ) {
v = Graph[ u ][ i ];
if( !dfn[ v ] ) {
Tarjan( v );
low[ u ] = min( low[ u ] , low[ v ] );
}
else if( is[ v ] )
low[ u ] = min( low[ u ] , dfn[ v ] );
}
if( dfn[ u ] == low[ u ] ) {
cnt ++;
do{
v = s.top();
is[ v ] = 0 , s.pop();
belong[ v ] = cnt;
num[ cnt ] ++;
}while( u != v );
}
}
struct node{
int v,w;
node(){}
node( int V , int W ) {
v = V;
w = W;
}
bool operator < ( const node &x ) const {
return w < x.w;
}
};
vector< int > lit_Graph1[ MAXN + 5 ];
vector< int > lit_Graph2[ MAXN + 5 ];
int dis1[ MAXN + 5 ],dis2[ MAXN + 5 ];
bool vis[ MAXN + 5 ];
void Spfa1( int s ) {
queue< int > Q;
while( !Q.empty() ) Q.pop();
for( int i = 1 ; i <= n ; i ++ ) dis1[ i ] = -0x3f3f3f3f;
memset( vis , 0 , sizeof( vis ) );
dis1[ s ] = 0 , vis[ s ] = 1;
Q.push( s );
while ( !Q.empty() ) {
int u = Q.front();
Q.pop() , vis[ u ] = 0;
for ( int i = 0 ; i < lit_Graph1[ u ].size() ; i ++ ) {
int v = lit_Graph1[ u ][ i ];
if ( dis1[ v ] < dis1[ u ] + num[ v ] ) {
dis1[ v ] = dis1[ u ] + num[ v ];
if ( !vis[ v ] ) {
vis[ v ] = 1;
Q.push( v );
}
}
}
}
}
void Spfa2( int s ) {
queue< int > Q;
while( !Q.empty() ) Q.pop();
for( int i = 1 ; i <= n ; i ++ ) dis2[ i ] = -0x3f3f3f3f;
memset( vis , 0 , sizeof( vis ) );
dis2[ s ] = 0 , vis[ s ] = 1;
Q.push( s );
while ( !Q.empty() ) {
int u = Q.front();
Q.pop() , vis[ u ] = 0;
for ( int i = 0 ; i < lit_Graph2[ u ].size() ; i ++ ) {
int v = lit_Graph2[ u ][ i ];
if ( dis2[ v ] < dis2[ u ] + num[ v ] ) {
dis2[ v ] = dis2[ u ] + num[ v ];
if ( !vis[ v ] ) {
vis[ v ] = 1;
Q.push( v );
}
}
}
}
}
int main( ) {
scanf("%d %d",&n,&m);
for( int i = 1 ; i <= m ; i ++ ) {
scanf("%d %d",&x,&y);
Graph[ x ].push_back( y );
}
for( int i = 1 ; i <= n ; i ++ )
if( !dfn[ i ] ) Tarjan( i );
for( int i = 1 ; i <= n ; i ++ )
{
for( int j = 0 ; j < Graph[ i ].size( ) ; j ++ ) {
int u = belong[ i ] , v = belong[ Graph[ i ][ j ] ];
if( u != v ) {
lit_Graph1[ u ].push_back( v );
lit_Graph2[ v ].push_back( u );
}
}
}
Spfa1( belong[ 1 ] );
Spfa2( belong[ 1 ] );
int Ans = num[ belong[ 1 ] ];
for( int i = 1 ; i <= cnt ; i ++ ) {
for( int j = 0 ; j < lit_Graph1[ i ].size( ) ; j ++ ) {
int u = i , v = lit_Graph1[ i ][ j ];
Ans = max( Ans , dis1[ v ] + dis2[ u ] + num[ belong[ 1 ] ] );
}
}
printf("%d\n",Ans);
return 0;
}